#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
public:
    // 思路：排序 + 双指针   把三数之和转化为两数之和
    // 1. 先对数组进行排序
    // 2. 遍历排序后的数组，固定一个数nums[i]，然后使用双指针在剩下的数组中寻找两个数，使得三数之和为0

    vector<vector<int>> threeSum(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        for (int i = 0; i < nums.size(); ++i)
        {
            // 1. 对a去重，如果当前数字和前一个数字相同，则跳过
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            // 2. 双指针寻找另外两个数
            int left = i + 1;            // 左指针
            int right = nums.size() - 1; // 右指针
            while (left < right)
            {
                if (nums[i] + nums[left] + nums[right] == 0) // 找到了一个三元组
                {
                    res.push_back({nums[i], nums[left], nums[right]});
                    ++left; // 移动左指针
                    // 注意：对b去重,while循环跳过所有与当前nums[left]相同的数字
                    while (left < right && nums[left] == nums[left - 1])
                    {
                        ++left;
                    }
                }
                else if (nums[i] + nums[left] + nums[right] < 0) // 和小于0，说明需要更大的数，移动左指针
                {
                    ++left;
                }
                else // 和大于0，说明需要更小的数，移动右指针
                {
                    --right;
                }
            }
        }
        return res;
    }
};